5.17

题目

Show that the Post Correspondence Problem is decidable over the unary alphabet
$Σ = {1}$ .

思路

点击展开

只需要上下 $1$ 的个数相同，记录第 $i$ 个骨牌中，下方 $1$ 个数与上方 $1$ 个数的差为 $a_{i}$ , 第 $i$ 个骨牌选取了 $x_{i}$ 次（ $x_{i} \geq 0$ , $x_{i}$ 不全为 $0$ ），问题就是判断是否存在这样的 $X$ 使得 $\sum_{i} a_{i} x_{i} = 0$

解答

点击展开

如果存在 $a_{k} = 0$ , 那么令 $x_{i} = [i = k]$ 即可，也就是只选取这一个骨牌，下面考虑其余情况：
将 $a_{i}$ 分为正负两部分，不妨设 $i \leq m$ 时, $a_{i} > 0$ . $i > m$ 时, $a_{i} < 0$

那么取

x_{i} = {\begin{aligned} \sum_{i = m + 1}^{n} - a_{i} & , i \leq m \\ \sum_{i = 1}^{m} a_{i} & , i > m \end{aligned}

这就满足了条件，需要特判的是只有正数或只有负数的情况

因此，图灵机工作方式如下：

$a_{i}$ 中存在 $0$ 就接受
$a_{i}$ 中有正有负就接受
否则拒绝